package test;

import java.lang.reflect.Array;
import java.util.*;
import java.util.Map.Entry;

/*
题目
347. 前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
数据
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
输入: nums = [1], k = 1
输出: [1]
 */
public class leetcode347_Kfrequent {
    //使用map保存，并进行全排序，复杂度为o(nlgn)
    public static List<Integer> topKFrequent(int nums[], int k) {
        //使用Map进行存储每个整数出现的次数
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i : nums) {
            Integer m = counts.get(i);//查看上一次是否有次数  获取方法一，自己手写
            if (m == null)  //每个数第一次遍历都设置为0
                m = 0;
            //Integer m=counts.getOrDefault(counts.get(i),0);  //获取方法二，后面那个0代表如果第一个是null就设置为0
            counts.put(i, m + 1);
        }
        //进行Map排序
        Map.Entry<Integer, Integer>[] entries = new Map.Entry[counts.size()];
        counts.entrySet().toArray(entries);   //将map转化为数组形式
        Arrays.sort(entries, (Entry<Integer, Integer> e1, Entry<Integer, Integer> e2) -> {
            return e2.getValue() - e1.getValue();   //降序操作
        });
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(entries[i].getKey());

        }
        return result;
    }
    //方法二  使用优先级队列进行排序
    public static List<Integer> topKFrequent1(int nums[], int k) {
        //使用Map进行存储每个整数出现的次数
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i : nums) {
            Integer m = counts.get(i);//查看上一次是否有次数  获取方法一，自己手写
            if (m == null)  //每个数第一次遍历都设置为0
                m = 0;
            counts.put(i, m + 1);
        }
        //使用优先级队列进行处理  ,最小堆每次调用remove，会删除里面最小的,最大堆每次调用remove，会删除里面最大的 复杂度为o(lgn)  PriorityQueue是最小堆
            PriorityQueue<Entry<Integer,Integer>> queue=new PriorityQueue<>((Entry<Integer,Integer> e1,Entry<Integer,Integer> e2)->{
            return e1.getValue()-e2.getValue();      //创建一个最小堆
        });
        for(Entry<Integer,Integer> e:counts.entrySet()){//拿出每一个Entry，加入到最小堆中
            if(queue.size()<k)  //不能取等，原因是这次会加入一个新的
                queue.add(e);
            else {
                if(queue.peek().getValue()>e.getValue());
                else {
                    queue.poll();
                    queue.add(e);
                }
            }
        }
    List<Integer> list=new LinkedList<>();
        while (!queue.isEmpty()){
            list.add(0,queue.remove().getKey());  //始终插入0号位置 后面自动后移
        }
        return list;
    }
//    //方法三 快速排序
//    public static List<Integer> topKFrequent2(int nums[], int k) {
//        //使用Map进行存储每个整数出现的次数
//        Map<Integer, Integer> counts = new HashMap<>();
//        for (int i : nums) {
//            Integer m = counts.get(i);//查看上一次是否有次数  获取方法一，自己手写
//            if (m == null)  //每个数第一次遍历都设置为0
//                m = 0;
//            counts.put(i, m + 1);
//        }
//        Entry<Integer,Integer> entry=
//        List<Integer> list=new LinkedList<>();
//        return list;
//    }

    public static void main(String[] args) {
        int nums[]={1,1,1,2,2,3};
        System.out.println(topKFrequent1(nums,1).toString());
    }
}
